package com.example.backtrack;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * 47. 全排列 II  与46.全排列的区别就是有重复元素（used作用多一个，且相应的需要先排序），那么此时used数组不仅标识使用状态，还要用来去重，此外全部一样
 * 给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有   !!!!!不重复的全排列!!!!!。
 * <p>
 * 示例 1：
 * <p>
 * 输入：nums = [1,1,2]
 * 输出：
 * [[1,1,2],
 * [1,2,1],
 * [2,1,1]]
 * 示例 2：
 * <p>
 * 输入：nums = [1,2,3]
 * 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
 */

public class PermutationsⅡ {

    /**
     * 存放符合条件结果的集合
     */
    List<List<Integer>> result = new ArrayList<>();
    /**
     * 用来存放符合条件结果
     */
    LinkedList<Integer> path = new LinkedList<>();
    boolean[] used;
    int[]nums;
    public static void main(String[] args) {
        PermutationsⅡ permutations = new PermutationsⅡ();
        int[] nums = {3, 1, 2};
        System.out.println(permutations.permuteUnique(nums));
    }

    public List<List<Integer>> permuteUnique(int[] nums) {
        used = new boolean[nums.length];
        this.nums=nums;
        Arrays.sort(nums);
        backTrack();
        return result;
    }

    private void backTrack( ) {
        if (path.size() == nums.length) {
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            // used[i - 1] == true，说明同⼀树⽀nums[i - 1]使⽤过
            // used[i - 1] == false，说明同⼀树层nums[i - 1]使⽤过
            // 如果同⼀树层nums[i - 1]使⽤过则直接跳过
            if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
                continue;
            }
            //如果同⼀树⽀nums[i]没使⽤过开始处理
            if (!used[i]) {
                //标记同⼀树⽀nums[i]使⽤过，防止同一树支重复使用
                used[i] = true;
                path.add(nums[i]);
                backTrack();
                //回溯，说明同⼀树层nums[i]使⽤过，防止下一树层重复
                path.remove(path.size() - 1);
                used[i] = false;//回溯
            }
        }
    }
}


class Permutation1 {
    List<String> res = new ArrayList<>();
    StringBuilder str = new StringBuilder();
    boolean[] used;
    char[] arr;

    public String[] permutation(String S) {
        int n = S.length();
        if (n <= 1) return new String[]{S};
        arr = S.toCharArray();
        Arrays.sort(arr);
        used = new boolean[n];
        back(n);
        String[] ss = new String[res.size()];
        return res.toArray(ss);
    }

    public void back(int n) {
        if (str.length() == n) {
            res.add(str.toString());
            return;
        }
        for (int i = 0; i < n; i++) {
            //用来去重
            if (i > 0 && arr[i] == arr[i - 1] && used[i - 1] == false) {
                continue;
            }
            //用来防止元素重复使用
            if (used[i]) continue;//
            used[i] = true;
            str.append(arr[i]);
            back(n);
            str.deleteCharAt(str.length() - 1);
            used[i] = false;
        }
    }
}

/**
 * 剑指 Offer 38. 字符串的排列
 * 输入一个字符串，打印出该字符串中字符的所有排列。
 * <p>
 * 你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。
 * <p>
 * 示例:
 * <p>
 * 输入：s = "abc"
 * 输出：["abc","acb","bac","bca","cab","cba"]
 */
class Permutation {
    List<String> list = new ArrayList<>();
    boolean[] bol;
    StringBuilder str = new StringBuilder();

    public String[] permutation(String s) {
        bol = new boolean[s.length()];
        char[] arr = s.toCharArray();
        //为了去重
        Arrays.sort(arr);
        back(s.length(), arr);
        String[] res = new String[list.size()];
        for (int i = 0; i < list.size(); i++) {
            res[i] = list.get(i);
        }
        return res;
    }

    public void back(int n, char[] arr) {
        if (str.length() == n) {
            list.add(str.toString());
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            if (i > 0 && arr[i] == arr[i - 1] && !bol[i - 1]) {
                continue;
            }
            if (!bol[i]) {
                bol[i] = true;
                str.append(arr[i]);
                back(n, arr);
                str.deleteCharAt(str.length() - 1);
                bol[i] = false;
            }
        }

    }
}



